package demo10;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;

/*
 * T一定要是非基础类型，有基础类型需求包一层
 */
public class HeapGreater<T> {

	private ArrayList<T> heap;//数组ArrayList
	private HashMap<T, Integer> indexMap;//反向索引表
	private int heapSize;//有效个数
	private Comparator<? super T> comp;//比较器

	public HeapGreater(Comparator<? super T> c) {//初始化
		heap = new ArrayList<>();
		indexMap = new HashMap<>();
		heapSize = 0;
		comp = c;
	}

	public boolean isEmpty() {
		return heapSize == 0;
	}

	public int size() {
		return heapSize;
	}

	public boolean contains(T obj) {
		//通过反向索引表来判断这个obj对象是否存在
		return indexMap.containsKey(obj);//
	}

	public T peek() {//原始peek
		return heap.get(0);//返回堆顶元素也就是下标为0的元素
	}

	public void push(T obj) {//将obj对象放在堆中
		heap.add(obj);//将其加载数组中
		indexMap.put(obj, heapSize);//将其加到反向索引表中
		heapInsert(heapSize++);//向上调整
	}

	public T pop() {//弹出堆顶元素
		T ans = heap.get(0);//先将要删除的元素保存下来
		swap(0, heapSize - 1);//将堆顶元素与最后一个元素交换
		indexMap.remove(ans);//将其要删除的元素从反向索引表移除
		heap.remove(--heapSize);//将删除的元素从堆中删除
		heapify(0);//将0下标向下调整
		return ans;//返回要删除的元素
	}

	public void remove(T obj) {//移除obj对象
		//移除元素思路 : 通过反向索引表得到要移除的元素下标,然后将最后一个元素设置到这个下标
		//将最后一个元素删除即可
		T replace = heap.get(heapSize - 1);//保存最后一个元素
		int index = indexMap.get(obj);//通过反向索引表得到要删除的元素下标
		indexMap.remove(obj);//将元素从反向索引表删除
		heap.remove(--heapSize);//将元素从堆中删除
		if (obj != replace) {//判断最后一个元素是否就是要删除的元素
			heap.set(index, replace);//将最后一个元素覆盖掉要删除的元素
			indexMap.put(replace, index);//同时更新反向索引表
			resign(replace);//调整堆
		}
	}

	public void resign(T obj) {//知道这个obj对象要调整,通过向上or向下调整
		heapInsert(indexMap.get(obj));
		heapify(indexMap.get(obj));
	}

	// 请返回堆上的所有元素
	public List<T> getAllElements() {
		List<T> ans = new ArrayList<>();
		for (T c : heap) {
			ans.add(c);
		}
		return ans;
	}

	//通过比较器向上调整
	private void heapInsert(int index) {
		while (comp.compare(heap.get(index), heap.get((index - 1) / 2)) < 0) {
			swap(index, (index - 1) / 2);
			index = (index - 1) / 2;
		}
	}

	//向下调整
	private void heapify(int index) {
		int child = index * 2 + 1;//得到左孩子
		while (child < heapSize) {
			if(child+1<heapSize && comp.compare(heap.get(child + 1), heap.get(child)) > 0){
				 child = child +1;
			}
			if(comp.compare(heap.get(index), heap.get(child)) < 0){
				swap(child,index);
				index = child;
				child = 2*index+1;
			}else {
				break;
			}
		}
	}

	private void swap(int i, int j) {
		T o1 = heap.get(i);
		T o2 = heap.get(j);
		heap.set(i, o2);
		heap.set(j, o1);
		indexMap.put(o2, i);
		indexMap.put(o1, j);
	}

}